package com.yuan.algorithms.动态规划;


/**
 * 给定一个序列，你有一次翻转该序列任意区间元素的机会，请找出该序列的最大累加和子序列
 * 例如给定[1,3,5,-10,10]
 * 翻转[-10,10]可得序列[1,3,5,10,-10]，最大累加和序列为[1,3,5,10]
 *
 * 解题思路：序列最大累加和dpMax[i] = Math.max(dpMax[i - 1] + arr[i], arr[i]);
 * 记录当前最大累加和curMax
 * 翻转后的最大累加和dpReverse[i] = Math.max(arr[i] + curMax, arr[i] + dpReverse[i - 1]);
 * @author YouYuan
 * @date 2022/3/20 1:05
 */
public class 找最大累加和序列_可翻转 {

    public static void main(String[] args) {
//        int[] arr = {1,3,5,-10,10};
//        int[] arr = {1,3,5,6,10};
//        int[] arr = {3,6,15,7,-12,-20,10 ,15,14,-10,-30,20,12};
        int[] arr = {-10,5,-5,30,20,-25,10,17,-30,5,6,9,-10,12};

        int[] dpMax = new int[arr.length];//记录最大累加和
        int[] dpReverse = new int[arr.length];//记录翻转累加和

        dpMax[0] = arr[0];
        dpReverse[0] = arr[0];
        int maxX = 0, maxY = 0, curMaxIndex = 0, curMax = Integer.MIN_VALUE;
        int reversX = 0, reversY = 0, tempX = 0, reversMax = Integer.MIN_VALUE;
        for (int i = 1; i < arr.length; i++) {
            int t = arr[i] + dpMax[i - 1];
//            dpMax[i] = Math.max(dpMax[i - 1] + arr[i], arr[i]);
            if (t >= arr[i]) {
                dpMax[i] = t;
            } else {
                //之前的序列和为负数，从当前位置开始找新的序列
                dpMax[i] = arr[i];
                //记录新的起点下标（不替换maxX是因为新的序列不一定比之前的序列大）
                tempX = i;
            }
            dpReverse[i] = Math.max(arr[i] + curMax, arr[i] + dpReverse[i - 1]);
            if (dpReverse[i] > reversMax) {
                reversMax = dpReverse[i];
                //新的翻转后累加和最大值，记录翻转下标
                reversX = curMaxIndex + 1;
                reversY = i;
            }
            if (t >= curMax) {
                maxX = tempX;
                maxY = i;
                // 更新当前最大累加和
                curMax = t;
                curMaxIndex = i;
            }
        }
        System.out.println("reversMax:" + reversMax);
        System.out.print("revers Seq:(%d,%d)   [".formatted(reversX, reversY) );
        for (int i = reversX; i <= reversY; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println("]");
        System.out.println("max Seq:(%d,%d)".formatted(maxX, maxY));
    }
}
